#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_TREES 3    // 森林中树的最大数量
#define MAX_NODES 30   // 所有树的最大结点总数
#define MAX_CHILDREN 2 // 每个结点的最大孩子数（二叉树）

// 双亲表示法结点结构
typedef struct
{
    int data;                   // 结点数据
    int parentIndex;            // 双亲结点索引（-1表示根结点）
    int childCount;             // 当前孩子数量
    int children[MAX_CHILDREN]; // 孩子结点索引数组
} PTNode;

// 森林结构
typedef struct
{
    PTNode nodes[MAX_NODES]; // 结点数组
    int roots[MAX_TREES];    // 每棵树的根结点索引
    int treeCount;           // 当前树的数量
    int nodeCount;           // 当前结点总数
} ParentTreeForest;

// 1. 初始森林
void InitForest(ParentTreeForest &F)
{
    F.treeCount = 0;
    F.nodeCount = 0;
    // 初始化所有结点
    for (int i = 0; i < MAX_NODES; i++)
    {
        F.nodes[i].data = -1;        // -1表示无效结点
        F.nodes[i].parentIndex = -1; // 初始无父结点
        F.nodes[i].childCount = 0;   // 初始无孩子
        for (int j = 0; j < MAX_CHILDREN; j++)
        {
            F.nodes[i].children[j] = -1; // -1表示无孩子
        }
    }
    // 初始化根结点数组
    for (int i = 0; i < MAX_TREES; i++)
    {
        F.roots[i] = -1; // -1表示该树为空
    }
}

// 2. 销毁森林
void DestroyForest(ParentTreeForest &F)
{
    // 重置所有结点
    for (int i = 0; i < MAX_NODES; i++)
    {
        F.nodes[i].data = -1;
        F.nodes[i].parentIndex = -1;
        F.nodes[i].childCount = 0;
        for (int j = 0; j < MAX_CHILDREN; j++)
        {
            F.nodes[i].children[j] = -1;
        }
    }
    // 重置根结点数组
    for (int i = 0; i < MAX_TREES; i++)
    {
        F.roots[i] = -1;
    }
    F.treeCount = 0;
    F.nodeCount = 0;
}

// 3. 插入结点（重点检查部分）
bool InsertNode(ParentTreeForest &F, int value, int parentIndex, int treeIndex, int childPosition)
{
    // 检查树索引有效性
    if (treeIndex < 0 || treeIndex >= MAX_TREES)
    {
        printf("Error: Invalid tree index\n");
        return false;
    }

    // 查找可用位置
    int newIndex = -1;
    for (int i = 0; i < MAX_NODES; i++)
    {
        if (F.nodes[i].data == -1)
        {
            newIndex = i;
            break;
        }
    }
    if (newIndex == -1)
    {
        printf("Error: Forest is full\n");
        return false;
    }

    // 设置新结点
    F.nodes[newIndex].data = value;
    F.nodes[newIndex].parentIndex = parentIndex;
    F.nodes[newIndex].childCount = 0;
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        F.nodes[newIndex].children[i] = -1;
    }

    // 处理根结点
    if (parentIndex == -1)
    {
        if (F.roots[treeIndex] != -1)
        {
            printf("Error: Tree root already exists\n");
            F.nodes[newIndex].data = -1;
            return false;
        }
        F.roots[treeIndex] = newIndex;
        F.treeCount++;
        F.nodeCount++;
        return true;
    }

    // 检查父结点有效性
    if (parentIndex < 0 || parentIndex >= MAX_NODES || F.nodes[parentIndex].data == -1)
    {
        printf("Error: Invalid parent node\n");
        F.nodes[newIndex].data = -1;
        return false;
    }

    // 检查孩子位置有效性
    if (childPosition < 0 || childPosition >= MAX_CHILDREN)
    {
        printf("Error: Invalid child position\n");
        F.nodes[newIndex].data = -1;
        return false;
    }

    // 检查父结点是否已有该位置的孩子
    if (F.nodes[parentIndex].children[childPosition] != -1)
    {
        printf("Error: Child position already occupied\n");
        F.nodes[newIndex].data = -1;
        return false;
    }

    // 检查父结点孩子数量
    if (F.nodes[parentIndex].childCount >= MAX_CHILDREN)
    {
        printf("Error: Parent has too many children\n");
        F.nodes[newIndex].data = -1;
        return false;
    }

    // 连接父结点和孩子
    F.nodes[parentIndex].children[childPosition] = newIndex;
    F.nodes[parentIndex].childCount++;
    F.nodeCount++;
    return true;
}

// 4.1 前序遍历（递归）
void PreOrder(ParentTreeForest F, int index)
{
    if (index == -1 || F.nodes[index].data == -1)
        return;

    printf("%d ", F.nodes[index].data); // 访问当前结点

    // 遍历所有孩子
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        if (F.nodes[index].children[i] != -1)
        {
            PreOrder(F, F.nodes[index].children[i]);
        }
    }
}

// 4.2 后序遍历（递归）
void PostOrder(ParentTreeForest F, int index)
{
    if (index == -1 || F.nodes[index].data == -1)
        return;

    // 先遍历所有孩子
    for (int i = 0; i < MAX_CHILDREN; i++)
    {
        if (F.nodes[index].children[i] != -1)
        {
            PostOrder(F, F.nodes[index].children[i]);
        }
    }

    printf("%d ", F.nodes[index].data); // 访问当前结点
}

// 4.3 层序遍历（队列实现）
void LevelOrder(ParentTreeForest F, int rootIndex)
{
    if (rootIndex == -1 || F.nodes[rootIndex].data == -1)
        return;

    int queue[MAX_NODES];
    int front = 0, rear = 0;

    queue[rear++] = rootIndex; // 根结点入队

    while (front < rear)
    {
        int index = queue[front++];
        printf("%d ", F.nodes[index].data); // 访问结点

        // 所有孩子入队
        for (int i = 0; i < MAX_CHILDREN; i++)
        {
            if (F.nodes[index].children[i] != -1)
            {
                queue[rear++] = F.nodes[index].children[i];
            }
        }
    }
}

// 4.4 森林遍历
void TraverseForest(ParentTreeForest F, const char *order)
{
    for (int i = 0; i < MAX_TREES; i++)
    {
        if (F.roots[i] == -1)
            continue;

        printf("Tree %d: ", i + 1);

        if (strcmp(order, "preorder") == 0)
        {
            PreOrder(F, F.roots[i]);
        }
        else if (strcmp(order, "postorder") == 0)
        {
            PostOrder(F, F.roots[i]);
        }
        else if (strcmp(order, "levelorder") == 0)
        {
            LevelOrder(F, F.roots[i]);
        }
        printf("\n");
    }
}

int main()
{
    ParentTreeForest F;
    InitForest(F);

    // 构建第一棵树 (1为根，2为左孩子，3为右孩子)
    InsertNode(F, 1, -1, 0, 0);         // 根结点
    InsertNode(F, 2, F.roots[0], 0, 0); // 左孩子
    InsertNode(F, 3, F.roots[0], 0, 1); // 右孩子

    // 构建第二棵树 (4为根，5为左孩子，6为右孩子)
    InsertNode(F, 4, -1, 1, 0);         // 根结点
    InsertNode(F, 5, F.roots[1], 1, 0); // 左孩子
    InsertNode(F, 6, F.roots[1], 1, 1); // 右孩子

    // 构建第三棵树 (7为根，8为左孩子，9为右孩子)
    InsertNode(F, 7, -1, 2, 0);         // 根结点
    InsertNode(F, 8, F.roots[2], 2, 0); // 左孩子
    InsertNode(F, 9, F.roots[2], 2, 1); // 右孩子

    // 遍历测试
    printf("Forest preorder traversal:\n");
    TraverseForest(F, "preorder");

    printf("\nForest postorder traversal:\n");
    TraverseForest(F, "postorder");

    printf("\nForest levelorder traversal:\n");
    TraverseForest(F, "levelorder");

    // 销毁森林
    DestroyForest(F);
    printf("\nForest destroyed\n");

    return 0;
}